#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

/* ------------------------------------------------------------------- */
/*
0   1   2       3   4   5       6   7   8
9   10  11      12  13  14      15  16  17
18  19  20      21  22  23      24  25  26

27  28  29      30  31  32      33  34  35
36  37  38      39  40  41      42  43  44
45  46  47      48  49  50      51  52  53

54  55  56      57  58  59      60  61  62
63  64  65      66  67  68      69  70  71
72  73  74      75  76  77      78  79  80
*/
/* ------------------------------------------------------------------- */
const int sudSolved[9][9] = {
    {6,3,4,9,1,5,7,2,8},
    {2,7,8,6,4,3,5,1,9},
    {5,9,1,2,7,8,6,4,3},
    {4,5,7,3,6,9,2,8,1},
    {9,8,6,4,2,1,3,5,7},
    {3,1,2,8,5,7,4,9,6},
    {1,2,5,7,8,6,9,3,4},
    {8,6,3,5,9,4,1,7,2},
    {7,4,9,1,3,2,8,6,5}
};
/* ------------------------------------------------------------------- */
const int sudBadHLine[9][9] = {
    {6,3,4,9,1,5,7,2,9},    //bad
    {2,7,8,6,4,3,5,1,8},    //bad
    {5,9,1,2,7,8,6,4,3},
    {4,5,7,3,6,9,2,8,1},
    {9,8,6,4,2,1,3,5,7},
    {3,1,2,8,5,7,4,9,6},
    {1,2,5,7,8,6,9,3,4},
    {8,6,3,5,9,4,1,7,2},
    {7,4,9,1,3,2,8,6,5}
};
/* ------------------------------------------------------------------- */
const int sudBadSq[9][9] = {
    {6,3,4,9,1,5,7,2,9},    //bad
    {2,7,8,6,4,3,5,1,8},    //bad
    {5,9,1,2,7,8,6,4,3},
    {4,5,7,3,6,9,2,8,1},
    {9,8,6,4,2,1,3,5,7},
    {3,1,2,8,5,7,4,9,6},
    {1,2,5,7,8,6,9,3,4},
    {8,6,3,5,9,4,1,7,2},
    {7,4,1,9,3,2,8,6,5}
};
/* ------------------------------------------------------------------- */
int countFree(int tab[9][9]) {
    int i, j, c = 0;
    for(i = 0; i < 9; i++)
        for(j = 0; j < 9; j++)
            if(tab[i][j] == 0)
                c++;
    return c;
}
/* ------------------------------------------------------------------- */
void printSud(int tab[9][9]) {
    int i, j;
    printf("\n");
    for(i = 0; i < 18; i++)
        printf("-");
    printf("-\n");
    for(i = 0; i < 9; i++) {
        printf("|");
        for(j = 0; j < 9; j++) {
            if(tab[i][j] == 0)
                printf(" |");
            else
                printf("%d|", tab[i][j]);
        }
        printf("\n");
        for(j = 0; j < 18; j++)
            printf("-");
        printf("-\n");
    }
    printf("\n");
}
/* ------------------------------------------------------------------- */

/* ------------------------------------------------------------------- */
int checkSud(int tab[9][9]) {
    int conflict = 0;
    //printf("checkSud\n");
    const int LSIZE = 10;
    int r, c, i, j, k, l[LSIZE], ptr;
    //squares
    for(r = 0; r < 9; r+=3) {
        for(c = 0; c < 9; c+=3) {
            //printf("----------------------\n");
            k = 0;
            memset((void*)l, 0, (size_t)(sizeof(int) * LSIZE));
            for(i = r; i < r+3; i++) {
                for(j = c; j < c+3; j++) {
                    ptr = tab[i][j];
                    //printf("i=%d,j=%d,ptr=%d\n", i, j, ptr);
                    if(l[ptr] == 0 || ptr == 0)
                        l[ptr]++;
                    else {
                        //printf("\nr=%d,c=%d,i=%d,j=%d,l[%d]=%d\n", r, c, i, j, ptr, l[ptr]);
                        conflict++;
                    }
                }
            }
        }
    }
    //h-lines
    for(i = 0; i < 9; i++) {
        memset(l, 0, sizeof(int) * LSIZE);
        for(j = 0; j < 9; j++) {
            ptr = tab[i][j];
            if(l[ptr] == 0 || ptr == 0) {
                l[ptr]++;
            } else {
                //printf("-2-");
                conflict++;
            }
        }
    }
    //v-lines
    for(j = 0; j < 9; j++) {
        memset(l, 0, sizeof(int) * LSIZE);
        for(i = 0; i < 9; i++) {
            ptr = tab[i][j];
            if(l[ptr] == 0 || ptr == 0) {
                l[ptr]++;
            } else {
                //printf("-3-");
                conflict++;
            }
        }
    }
    //printf("-4-");
    return conflict;
}
/* ------------------------------------------------------------------- */
void genSud(int tab[9][9]) {
    int i, j, r, v;

	while(countFree(tab) > 0 || checkSud(tab) > 0) {
		memset(tab, 0, sizeof(int) * 9 * 9);
		for(v = 1; v < 10; v++) {
			for(i = 0; i < 9; i++) {
				j = rand() % 9;
				while(tab[i][j] != 0 ) {
					j = rand() % 9;	
				}
				tab[i][j] = v;
			}
		}
		printSud(tab);
	}
	
	return;

    i = rand() % 9;
    j = rand() % 9;

    while(countFree(tab) > 0 && tab[i][j] != 0) {
        i = rand() % 9;
        j = rand() % 9;
		printf("DD");
    }

    tab[i][j] = (rand() % 9) + 1;
    while(checkSud(tab) > 0) {
		r = (rand() % 9) + 1;
        tab[i][j] = r;
		printf("r=%d, tab[%d][%d]=%d\n", r, i, j, tab[i][j]);
		printSud(tab);
    }
}
/* ------------------------------------------------------------------- */
void rozpSud(int tab[9][9], int solvedList[9][9][10], int * solPtr) {
    int i, j, v;
    for(i = 0; i < 9; i++) {
        for(j = 0; j < 9; j++) {
            if(tab[i][j] == 0) {
                for(v = 1; v < 10; v++) {
                    tab[i][j] = v;
                    if(checkSud(tab) == 0) {
						printSud(tab);
                        if(countFree(tab) > 0) {
                            rozpSud(tab, solvedList, solPtr);
                        } else {
                            //memcpy(solvedList[*solPtr], tab, sizeof(int)*9*9);
                            //(*solPtr)++;
                            printf("SOLVED!!!!");
	                    }
					}
                }
            }
        }
    }
}
/* ------------------------------------------------------------------- */
int main()
{
    time_t seconds;
    time(&seconds);
    srand((unsigned int) seconds);

    int sudoku[9][9] ;
    int solvList[9][9][10];
    int n, N = 45, solvCount;

    memset(sudoku, 0, sizeof(int) * 9 * 9);
    memset(solvList, 0, sizeof(int) * 9 * 9 * 10);
    solvCount = 0;

	printSud(sudoku);

	genSud(sudoku);
	
	printSud(sudoku);
	
		

    //rozpSud(sudoku, solvList, &solvCount);

//    printSud(sudoku);
//    printSud(&solvList[0]);

    return 0;
}
/* ------------------------------------------------------------------- */
